package Array;

/**
 * 53.Maximum Subarray（最大子序和）
 * https://leetcode.com/problems/maximum-subarray/
 *
 * Given an integer array nums, find the contiguous(连续) subarray (containing at least one number)
 * which has the largest sum and return its sum.
 *
 * Example:
 *
 * Input: [-2,1,-3,4,-1,2,1,-5,4],
 * Output: 6
 * Explanation(解释): [4,-1,2,1] has the largest sum = 6.
 *
 * Follow up(进阶):
 *
 * If you have figured out the O(n) solution,
 * try coding another solution using the divide and conquer approach(分治法),
 * which is more subtle(精妙).
 */
public class E_53_最大子序和 {
    /**
     * 暴力法：不推荐
     * 使用两个遍历，分别算出每种子序列的和
     */
    public static int maxSubArray10(int[] nums) {
        int length = nums.length;
        int maxSum = 0;
        for (int i = 0; i < length; i++) {
            int temp = 0;
            for (int j = i; j < length; j++) {
                temp = temp + nums[j];
                maxSum = Math.max(maxSum, temp);
            }
        }
        return maxSum;
    }

    /**
     * 网上找到的一种思想，但是不是很明白什么意思？？？
     */
    public static int maxSubArray1(int[] nums) {
        int sum = 0, maxSum = 0, minSum = 0;
        for (int num: nums) {
            sum += num;
            maxSum = Math.max(maxSum, sum-minSum);
            minSum = Math.min(minSum, sum);
            System.out.println(sum + " " + maxSum + " " + minSum);
        }
        return maxSum;
    }

    /**
     * 使用动态规划进行解决
     * currMaxSum： 累计最大和到当前位置i
     * maxSum：全局最大子序列和
     */
    public static int maxSubArray2(int[] nums) {
        int maxSum = nums[0], currMaxSum = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, currMaxSum);
        }
        return maxSum;
    }

    /**
     * 使用贪心法解决
     * 累加，如果和<0则重新开始
     */
    public static int maxSubArray3(int[] nums) {
        int maxSum = nums[0];
        int sum = 0;
        for (int num: nums) {
            sum += num;
            if (sum < 0) {
                sum = 0;
            } else {
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }

    /**
     * 分治法
     *
     * 把数组nums以中间位置（m)分为左（left)右(right)两部分. 那么有，
     * left = nums[0]...nums[m - 1] 和 right = nums[m + 1]...nums[n-1]
     *
     * 最大子序列和的位置有以下三种情况：
     * 1.考虑中间元素nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。
     * 2.不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
     * 3.不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和
     * 分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。
     * 如下图片
     * https://camo.githubusercontent.com/dfbf75bebf1618655527ed5dbb9f376a527d9817/68747470733a2f2f747661312e73696e61696d672e636e2f6c617267652f303038327a7962706c7931676276336867756961646a333134303075303434742e6a7067
     */
    public static int maxSubArray4(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return helper(nums, 0, nums.length - 1);
    }

    private static int helper(int[] nums, int l, int r) {
        if (l > r) return Integer.MIN_VALUE;
        int mid = (l + r) >>> 1;
        int left = helper(nums, l, mid - 1);
        int right = helper(nums, mid + 1, r);
        int leftMaxSum = 0;
        int sum = 0;
        // left surfix maxSum start from index mid - 1 to l
        for (int i = mid - 1; i >= l; i--) {
            sum += nums[i];
            leftMaxSum = Math.max(leftMaxSum, sum);
        }
        int rightMaxSum = 0;
        sum = 0;
        // right prefix maxSum start from index mid + 1 to r
        for (int i = mid + 1; i <= r; i++) {
            sum += nums[i];
            rightMaxSum = Math.max(sum, rightMaxSum);
        }
        // max(left, right, crossSum)
        return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
    }

    public static void main(String[] args) {
        System.out.println(maxSubArray3(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
